#include <mips/regdef.h>
#define STACKSP 48
#define STACKRA 40
#define	STACKFP 36
#define STACKGP 32
#define LA 16
#define ABA 0

//#52 a1=arraysize		#***************#
//#48 a0=words	               #*ABA de la caller*#
//#44 --pad--			#***************#
//#40 $ra			#***************#
//#36 $fp			#***************#
//#32 $gp			#******SRA******#
//#28 increment			#***************#
//#24 temp			#***************#
//#20 j				#***************#
//#16 i                         #*******LA******#
//#12 a3			#***************#
//#8 a2				#***************#
//#4 a1			        #***************#
//#0 a0			       #*ABA de shellsort*#
//#-----------#	

	.text
	.align 2
	.globl shellsort
	.ent shellsort

shellsort:
	.frame $fp, STACKSP, ra
	.set noreorder
	.cpload t9
	.set reorder

	#Creacion del Stack frame
	subu sp,sp,STACKSP
	.cprestore STACKGP

	#Guardo los reg de la SRA
	sw ra, STACKRA(sp)
	sw $fp, STACKFP(sp)	
	move $fp,sp
	
	#Argument Building Area
	sw a0,STACKSP($fp) 	#Guardo words en el ABA de la caller
	sw a1,STACKSP+4($fp)    #Guardo arraysize en el ABA de la caller
	
	#Guardo variables locales 
	sw zero,LA+0($fp)         #i<-0 , Inicializo en 0 a i
	sw zero,LA+4($fp) 	  #j<-0 , Inicializo en 0 a j
	sw zero,LA+8($fp) 	  #temp<-0 , Inicializo en 0 a temp
	divu t0,a1,2		  
	sw t0,LA+12($fp)	  #increment<-t0<-arraysize/2 , Inicializo a increment en arraysize/2
	
	
	
	#Levanto en registros temporales los argumentos y las variables locales
	lw t0, STACKSP($fp)   #t0<-&words
	lw t1, LA+0($fp)      #t1<-i
	lw t2, LA+4($fp)      #t2<-j
	lw t3, LA+8($fp)      #t3<-temp
	lw t4, LA+12($fp)     #t4<-increment
	lw t5, STACKSP+4($fp) #t5<-arraysize
	
whileexterno: blez t4, finwhileexterno       #Si increment<=0 termino el while 
	      move t1,zero             #Si no termine el while, inicializo i en 0

for:	bge t1,t5, finfor	 #si i>=arraysize termine el for
	move t2,t1 		 #j<-i
	mul t7,t1,4		  #t7<-(4*i)
	addu t3,t0,t7             #temp<-&words[i]
	lw t3,0(t3)		 #temp<-words[i]
		
whileinterno:     bge t2,t4,checkCondicion2   #Si j>=increment tengo que verificar la otra condicion
		  b finwhileinterno  #Si no cumple entonces ya salgo del while interno

checkCondicion2:  #Preparo para la llamada a StrCmpp, guardo las variables locales
		  sw t0, STACKSP($fp)
		  sw t1,LA+0($fp)
		  sw t2,LA+4($fp)
		  sw t3,LA+8($fp)
		  sw t4,LA+12($fp)
	          subu t2,t2,t4     #t2<-j-increment
		  mul t6,t2,4	   #t6<-(j-increment)*4
		  addu t6,t0,t6     #t6<-&words[j-increment]
		  lw a0,0(t6)     #a0<-words[j-increment] Argumento 1 a comparar por MyStrCmp
		  move a1,t3	  #a1<-temp Argumento 2 a comparar por MyStrCmp
		  jal MyStrCmp
		  #Levanto en registros los valores de las variables locales por si cambiaron los temporales
		  lw t0, STACKSP($fp)   #t0<-&words
		  lw t1, LA+0($fp)      #t1<-i
	          lw t2, LA+4($fp)      #t2<-j
	          lw t3, LA+8($fp)      #t3<-temp
	          lw t4, LA+12($fp)    	 #t4<-increment
	          lw t5, STACKSP+4($fp)	 #t5<-arraysize
		  
		  blez v0, finwhileinterno 	#Si el resultado de StrCmpp fue menor o igual que 0, termino el while interno
		  subu t6,t2,t4       #t6<-j-increment
		  mul t6,t6,4	     #t6<-(j-increment)*4
		  addu t6,t0,t6       #t6<-&words[j-increment]
		  mul t7,t2,4	     #t7<-(j*4)
		  addu t7,t0,t7       #t7<-&words[j]
		  lw t6,0(t6)
		  sw t6,(t7)	     #words[j]<-&words[j-increment]
		  subu t2,t2,t4	     #j<-j-increment
		  b whileinterno
finwhileinterno: 
		mul t7,t2,4	     #t7<-(j*4)
		addu t7,t0,t7       #t7<-&words[j]
		sw t3,(t7)	   #words[j] apunte a temp
		addu t1,t1,1        #i++
		b for 
finfor: bne t4,2,else       #Si increment es distinto de 2 salto
		    li t4,1             #si es igual a 2 lo pongo en 1 y vuelvo al while externo
		   b whileexterno
else: 	mul t4,t4,5             #si es distinto de 2, lo mutiplico por 5/11 y vuelvo al while externo
	divu t4,t4,11
	b whileexterno
finwhileexterno:
	#Restauro los registros de la SRA
	lw $fp,STACKFP(sp)  #Restauro fp
	lw ra,STACKRA(sp)  #Restaura ra
	
   	#Destruyo el stack frame
   	addu sp,sp,STACKSP
   	j ra

.end shellsort
